//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/553546931/

class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int& p, int inbegin, int inend)
    {
        if (inbegin > inend)
            return NULL;

        //确定根节点
        TreeNode* root = new TreeNode(preorder[p]);

        //利用根节点区分左右区间
        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (preorder[p] == inorder[rooti]) break;
            else
                rooti++;
        }

        //前序构建左右子树
        p++;
        root->left = build(preorder, inorder, p, inbegin, rooti - 1);
        root->right = build(preorder, inorder, p, rooti + 1, inend);

        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        TreeNode* root = build(preorder, inorder, i, 0, inorder.size() - 1);

        return root;

    }
};